package Sort_Code;

public class InsertSort {
    //插入排序
    //认定左边为有序，遍历右边无序插入到左边有序的适当位置
    public static void main(String[] args) {
        int[] arr={9,10,4,8,6,2,3,1,7,5};
        //找出无序数组的起始索引,减少前面的比较，提高效率
        int startpos=-1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>arr[i+1]){
                startpos=i+1;
                break;
            }
        }

        for(int i=startpos;i<arr.length;i++){
            if(arr[i]>=arr[i-1]){
                continue;
            }
            else{
                //记录当前插入的值的索引
                int k=i;

                for(int j=i-1;j>=0;j--){
                    if(arr[k]<arr[j]){
                        int t=arr[k];
                        arr[k]=arr[j];
                        arr[j]=t;
                        k--;
                    }
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
